/*1 排序 2 查找 3 比较 ----RunTime: 380ms*/


#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

void print(int *nums, int len)
{
	int i;
	for(i = 0; i < len; i++)
		printf("%d ", nums[i]);
	printf("\n");
}

// 排序
#if 1
void sort(int *nums, int *pOrders, int l, int h, int len)
{
	//152ms
	int low = l, high = h;
     
    if (low >= high)
        return;
	int ran;
	ran = (low + high) / 2;
    swap(&nums[ran], &nums[low]);
    swap(&pOrders[ran], &pOrders[low]);
	    int target = nums[low];
	
    while (low < high) {
        while (nums[high] >= target && low < high )
            high--;
        nums[low] = nums[high];
        swap(pOrders + low, pOrders + high);
         
        while (nums[low] <= target && low < high)
            low++;
        nums[high] = nums[low];
        swap(pOrders + high, pOrders + low);
		print(nums, len);
		printf("low%d key%d i=%d j=%d\n", l, target, low, high);
    }
    nums[low] = target;
     
    sort(nums, pOrders, l, low - 1, len);
    sort(nums, pOrders, high + 1, h, len);
}
#else
void sort(int *nums, int *pOrders,int low, int high, int len)
{
	//3ms
	int key, i, j, ran;
    if (low < high)
    {
        ran = (low + high) / 2;
        swap(&nums[ran], &nums[low]);
        swap(&pOrders[ran], &pOrders[low]);
        key = nums[low];
        i = low + 1;
        j = high;
        while (i <= j)
        {
            while ((i <= high) && (nums[i] <= key))
                i++;
            while ((j >= low) && (nums[j] > key))
                j--;
            if (i < j)
            {
                swap(&nums[i], &nums[j]);
                swap(&pOrders[i], &pOrders[j]);
            }
			print(nums, len);
			//printf("low%d key%d i=%d j=%d\n", low, key, i, j);
        }
		if(low != j)
		{
			swap(&nums[low], &nums[j]);
			swap(&pOrders[low], &pOrders[j]);
		}
        sort(nums, pOrders, low, j - 1, len);
        sort(nums, pOrders, j + 1, high, len);
    }
}
#endif


int search(int *nums, int numsSize, int target, int index)
{
	int low, high;
	int mid;
	int len = numsSize;
	int i, j;
	
	low = 0;
	high = len - 1;
	
	for(i = 0; i < len; i++)
	{
		mid = (low+high)/2;
		//printf("%d %d %d[%d]\n", nums[low], nums[mid], nums[high], target);
		if(target < nums[mid])
		{
			high = mid;
			mid = (high+low)/2;
		}
		else if(target > nums[mid])
		{
			low = mid;
			mid = (high+low)/2;
		}
		else if(target == nums[mid])
		{
			if(mid != index)
				return mid;
		}
		else
			return -1;
	}
	return -1;
}

int* twoSum(int* nums, int numsSize, int target)
{
	int *pNums = nums;
	int len = numsSize;
	int *ret;
	int *pOrders;
	int i, tmp;
	
	ret = (int *)malloc(sizeof(int)*2);
	pOrders = (int *)malloc(sizeof(int)*len);
	
	for(i = 0; i < len; i++)
	{
		pOrders[i] = i;
	}
	sort(pNums, pOrders, 0, len - 1, len);
	print(nums, len);

	for(i = 0; i < len; i++)
	{
		tmp = search(pNums, len, target-pNums[i], i);
		if(-1 != tmp)
		{
			ret[0] = pOrders[tmp];
			ret[1] = pOrders[i];
			printf("%d %d\n", ret[0], ret[1]);
			break;
		}
	}
	return ret;
}

int main(void)
{
	int num[] = {3,4,9,7,2,10,1,5};
	int target = 11;
	int twoNum[2];
	twoSum(num, 8, target);
	return 0;
}